Distance

어떠한 Vector space 상에서 두 Data point간의 거리를 측정하는 방법.

$d (a, b)$ : element $a, b$ 사이의 거리를 나타내는 function.

Minkowski distance of order p

두 점 사이의 거리를 일반화한 형태.

d (a, b) \equiv (i \sum ∣ a_{i} - b_{i} ∣^{p})^{1/ p}

City block distance

L1 norm, 혹은 Manhattan distance 라고도 한다.
$d (a, b) \equiv i \sum ∣ a_{i} - b_{i} ∣ \equiv ∥ a - b ∥_{1}$

Euclidean distance

L2 norm.
$d (a, b) \equiv i \sum (a_{i} - b_{i})^{2} \equiv ∥ a - b ∥_{2}$

Chebyshev distance

두 점 사이의 최대 자표 차이로 계산되는 거리. 각 차원의 차이 중 가장 큰 값만을 이용한다. 이동할 수 있는 모든 방향에 같은 cost가 발생한다면 유용하다.
$∥ x ∥_{\infty} = i max ∣ x_{i} ∣ = i max ∣ a_{i} - b_{i} ∣$

Mahalonobis distance

데이터의 분포를 고려한 Distance 측정 방법. 데이터의 공분산을 반영하여 두 점 사이의 거리를 계산한다.

데이터가 퍼져 있는 방향과 스케일을 고려하여 계산되므로, 데이터가 비등방성(Anisotropy, 방향에 따라 성질이 다름)일 때 유용하다.

d (a, b) \equiv (a - b) Σ^{- 1} (a - b) \approx i \sum \frac{( a _{i} - b _{i} ) ^{2}}{σ _{i}^{2}}

Variance가 큰 차원에서는 차이가 작게 반영되고, 작은 차원에서는 차이가 크게 반영된다. 즉, 데이터가 퍼져있는 방향에 따라 다른 거리로 계산된다.

즉, Variance의 정도를 반영하여 각 차원의 거리가 계산되므로 regularization이 이루어지게 된다.